package main

import (
	"math"
)

// 279. 完全平方数
// https://leetcode-cn.com/problems/perfect-squares/

// 四平方和定理
// 		任何正整数都可以拆分成不超过4个数的平方和 ---> 答案只可能是1,2,3,4
// 如果一个数最少可以拆成4个数的平方和，则这个数还满足 n = (4^a)*(8b+7) ---> 因此可以先看这个数是否满足上述公式，如果不满足，答案就是1,2,3了
// 如果这个数本来就是某个数的平方，那么答案就是1，否则答案就只剩2,3了
// 如果答案是2，即n=a^2+b^2，那么我们可以枚举a，来验证，如果验证通过则答案是2
// 只能是3
func numSquares(n int) int {
	// 校验是否满足 n = (4^a)*(8b+7)
	for n&3 == 0 {
		n >>= 2 // 4^a
	}
	if n&7 == 7 {
		return 4 // 8b+7
	}
	if isSquare(n) {
		return 1
	}
	for i := 1; float64(i) < math.Sqrt(float64(n)); i++ {
		if isSquare(n - i*i) {
			return 2
		}
	}
	return 3
}

func isSquare(n int) bool {
	sq := int(math.Sqrt(float64(n)))
	return sq*sq == n
}

func main() {
	req := numSquares(11)
	println(req)

}
